package C024;

import java.util.Arrays;

/**
 * ClassName: Main
 * Package: C024
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/12/9 16:14
 * @Version 1.0
 * @Since 1.0
 */
public class Main {
    public static void main(String[] args) {
        int n = 1000;
        int size = 100;
        int length = 20;

        int k;
        for (int i = 0; i < n; i++) {
            int[] arr1 = randomGenerateArr(size, length);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);
            k = (int) (Math.random() * length) + 1;
            int n1 = violence(arr1, k);
            int n2 = findKthLargest(arr2, k);
            if (n1 != n2) {

                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println(Arrays.toString(arr3));
                System.out.println("error !!!");
                System.out.println(n1 + " " + n2 + " " + k);
                return;
            }
        }

        System.out.println("success !!!");
    }


    public static int[] randomGenerateArr(int size, int length) {
        int[] ints = new int[length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = (int) (Math.random() * size);
        }
        return ints;
    }

    public static int violence(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }


    public static int findKthLargest(int[] nums, int k) {
        return process(nums, nums.length - k, 0, nums.length - 1);
    }

    private static int process(int[] nums, int k, int l, int r) {
        int randomIndex;
        while (l <= r) {
            randomIndex = l + (int) (Math.random() * (r - l + 1)); // l ... r
            int[] res = partitionForThree(nums, l, r, randomIndex);
            if (k < res[0] + 1) {
                r = res[0];
            } else if (k > res[1] - 1) {
                l = res[1];
            } else {
                return nums[k];
            }
        }
        return -1;
    }


    /**
     * 三区划分
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int[] partitionForThree(int[] arr, int l, int r, int index) {
        int ml = l;
        int mr = r;
        int num = arr[index];
        int i = l;
        while (i <= mr) {
            if (arr[i] < num) {
                swap(arr, ml++, i++);
            } else if (arr[i] == num) {
                i++;
            } else if (arr[i] > num) {
                swap(arr, mr--, i);
            }
        }
        return new int[]{ml - 1, mr + 1};
    }

    private static void swap(int[] arr, int m, int i) {
        int temp = arr[m];
        arr[m] = arr[i];
        arr[i] = temp;
    }
}
